package leetcode;

/**
 * 2.两数相加
 *
 * <p>
 * 给出两个非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
 * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
 * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头
 * <p>
 * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
 * 输出：7 -> 0 -> 8
 * 原因：342 + 465 = 807
 * <p>
 * 哑结点，不返回
 *
 * @author: cuihao
 * @create: 2020-05-05 16:31
 **/
public class AddTwoNumbers {

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        if (l1 == null && l2 == null) {
            return new ListNode(0);
        }
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode tail1 = l1;
        ListNode tail2 = l2;

        boolean beyond = false;
        ListNode head = new ListNode(-1);
        ListNode next = head;


        while (tail1 != null || tail2 != null || beyond) {

            int t1 = tail1 != null ? tail1.val : 0;
            int t2 = tail2 != null ? tail2.val : 0;
            int sum = beyond ? t1 + t2 + 1 : t1 + t2;
            int cur = sum % 10;
            beyond = sum > 9;

            ListNode newNode = new ListNode(cur);
            next.next = newNode;
            next = newNode;

            tail1 = tail1 != null ? tail1.next : null;
            tail2 = tail2 != null ? tail2.next : null;

        }
        return head.next;
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(4);
        ListNode listNode3 = new ListNode(3);
        listNode1.next = listNode2;
        listNode2.next = listNode3;

        ListNode listNode4 = new ListNode(5);
        ListNode listNode5 = new ListNode(6);
        ListNode listNode6 = new ListNode(4);
        listNode4.next = listNode5;
        listNode5.next = listNode6;

        ListNode listNode = addTwoNumbers(listNode1, listNode4);

        System.out.println(listNode);
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
